
package dijkstra;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.Scanner;
import gdatastructure.Graph;
import java.util.ArrayList;
import java.util.List;

public class Dijkstra {
	
	double dvalue[];
	int shortest[];
	int source = 0;
	List list = new ArrayList();
	private Graph mygraph;
	
	public Dijkstra(Graph mygraph){
		this.mygraph = mygraph;
		dvalue = new double[mygraph.size() + 1];
		shortest = new int[mygraph.size() + 1];
	}
	public void userInterface()//使用界面
	{
		System.out.println("/*** The K short path ***/");
		System.out.println("Input your source node:");
		System.out.print("$");
		BufferedReader in =new BufferedReader(new InputStreamReader( System.in));
		try{
			this.source = Integer.parseInt(in.readLine().trim());
		}catch(Exception e)
		{
			
		}
             
		runDijkstra();
		showResults();
                
	}
        
    
	private void initializeSingleSource()//初始化一个图
	{
		for(int i = 1; i <= mygraph.size(); i++)
		{
			dvalue[i] = -1; // -1 is the maximum value
			shortest[i] = 0;
		}
		dvalue[source] = 0;
	}

	private void relax(int u, int v, double w)//宽松算法，不用调用
	{
		double edgevalue = mygraph.getEdgeValue(u, v);
		if(dvalue[v] == -1 || dvalue[v] > dvalue[u] + edgevalue)
		{
			dvalue[v] = dvalue[u] + edgevalue;
			shortest[v] = u;
		}
	}
	//运行Dijkstra算法
	public void runDijkstra()//运行调运
	{
	
		this.source = source;
		initializeSingleSource();
		//初始化结点集合S和Q
		LinkedList<Integer> S = new LinkedList<Integer>();
		LinkedList<Integer> Q = new LinkedList<Integer>();
		for(int i = 1; i <= mygraph.size(); i++)
			Q.add(i);
		while(Q.size() != 0)
		{
			ListIterator<Integer> iterator1 = Q.listIterator();
			ListIterator<Integer> iterator2 = null; //迭代器的定义
			double minvalue = -1;
			int minpos = -1;
			while(iterator1.hasNext())
			{
				int curpos = iterator1.next();
				if((minvalue == -1 || dvalue[curpos] < minvalue) && dvalue[curpos] != -1)
				{
					minvalue = dvalue[curpos];
					minpos = curpos;
				}
			}
			Q.remove(Q.indexOf(new Integer(minpos)));//集合Q去掉最近点
			S.add(minpos);							//集合S加入最近点
			
			iterator2 = mygraph.getAllNeighbours(minpos).listIterator();//iterator2为minpos所有邻接点迭代器  minpos参数放入结点的下标
			while(iterator2.hasNext())
			{
				int pos = iterator2.next();//此时的pos为所求结点的下标
				relax(minpos, pos, mygraph.getEdgeValue(minpos, pos));
 			}
		}
	}
	//递归法打印最短路径
	private void printfPath(int source, int dest)
	{
		if(dest == source)
                {
                    System.out.print(source);
                    list.add(source);
                }
			
               
		else
		{
			printfPath(source, shortest[dest]);
			System.out.print("->" + dest);
                    list.add(dest);
		}
	}
	//打印结果
	public void showResults()
	{
		System.out.println("/*** The  Results, source point is " + source+ " ***/");
		while(true)
		{
		System.out.println("Please input the terminal ( 1 to 264346 and 0 stand for quit ) ");
		System.out.println("$");
		int i;
		Scanner sc = new Scanner(System.in);   
		i=sc.nextInt(); 
		if(i==0)
			break;
		else
		if(dvalue[i] != -1 && i != source)
			{
				System.out.println("*******************");
				System.out.println("To node [" + i + "]");
				System.out.println("Minimum path length: " + dvalue[i]);
                                System.out.println("/*** SHORTEST[] ***/");
                                int k;
               
				printfPath(source, i); 
                               
				System.out.println("");
				
			}
		}
		
//		for(int i = 1; i <= mygraph.size(); i++)
//		{
//			if(dvalue[i] != -1 && i != source)
//			{
//				System.out.println("*******************");
//				System.out.println("To node [" + i + "]");
//				System.out.println("Minimum path length: " + dvalue[i]);
//				printfPath(source, i);
//				System.out.println("");
//				
//			}
//		}
		System.out.println("*******************");
		System.out.println("");
	}
        
}
